#!/usr/bin/env python

# Code Generator for the Simple LISP Dialect for Teaching
#
# Author:   Mike Murphy <mamurph@cs.clemson.edu>
# Revision: 17 January 2009
#
# Copyright 2008-2009 Clemson University
#
# Permission is hereby granted, free of charge, to any person obtaining a
# copy of this software and associated documentation files (the "Software"),
# to deal in the Software without restriction, including without limitation
# the rights to use, copy, modify, merge, publish, distribute, sublicense,
# and/or sell copies of the Software, and to permit persons to whom the
# Software is furnished to do so, subject to the following conditions:
#
# The above copyright notice and this permission notice shall be included in
# all copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
# IN THE SOFTWARE.
#
# This material is based upon work supported under a National Science
# Foundation Graduate Research Fellowship. Any opinions, findings,
# conclusions or recommendations expressed in this publication are those of
# the author(s) and do not necessarily reflect the views of the National
# Science Foundation.

import sys
from parser import Parser
from symbol_table import SymbolTable
from shared_config import CompilerException, PRELOADED_SYMBOLS, SCAN_TYPES
from type_checker import TypeChecker

# Control debugging and trace messages for *this module only*
DEBUG=False
TRACE=False

# Starting value for Jasmin labels
LABEL_START=1


# Debug and trace routines
def dbg(msg):
   if DEBUG:
      print >> sys.stderr, '*G:DEBUG*:', msg
#

def trace(msg):
   if TRACE:
      print >> sys.stderr, '*G:TRACE*:', msg
#


# Code generator class
class CodeGenerator(object):
   def __init__(self, filename, classname, fh, interactive = False):
      self.filename = filename
      self.classname = classname
      self.fh = fh
      self.interactive = interactive
      self.line = 0
      self.last_line = 0
      self.symbol_table = SymbolTable(PRELOADED_SYMBOLS)
      #
      self.parser = Parser(self.fh)
      self.type_checker = TypeChecker(self.parser, self.symbol_table)
      #
      # The code generator output buffer is just a list of lines. We don't
      # print output directly, due to the need to print a header at the top
      # of the output when compiling non-interactively (and the need to wrap
      # each outer statement in a method when compiling interactively).
      self.output = []
      self.labelnum = LABEL_START
      #
      self.oper_map = { ('+',  1) : self.unary_plus,
                        ('+',  2) : self.binary_plus,
                        ('-',  1) : self.unary_minus,
                        ('-',  2) : self.binary_minus,
                        ('*',  2) : self.binary_mult,
                        ('/',  2) : self.binary_div,
                        ('%',  2) : self.binary_mod,
                        ('<',  2) : self.binary_lt,
                        ('<=', 2) : self.binary_le,
                        ('>',  2) : self.binary_gt,
                        ('>=', 2) : self.binary_ge,
                        ('=',  2) : self.binary_eq,
                        ('!=', 2) : self.binary_ne,
                        ('!',  1) : self.unary_not,
                        # "if" is a special case
                      }
   #
   def putLine(self, codeline, indent):
      '''Adds a line to the output buffer'''
      self.output.append(' ' * indent + codeline)
      # Add a line number to the most recently appended line, if there is
      # space and the line number has changed from the last line number added
      if self.line > self.last_line:
         length = len(self.output[-1])
         if length < 67:
            spaces = 76 - length - 10
            self.output[-1] += (' ' * spaces) + ('; line: %02d' % self.line)
            self.last_line = self.line
   #
   def getStackLimit(self):
      '''Returns the value for the Jasmin .limit stack directive'''
      # The type-checker now accounts for the extra stack item when printing,
      # so the "add 1" hack is no longer needed
      return self.type_checker.getStackLimit()
   def getLabel(self):
      '''Returns a Jasmin label and increments the label number'''
      num = self.labelnum
      self.labelnum += 1
      return ('label_%d' % num)
   #
   def implicit_print(self):
      '''Appends Jasmin code to handle the implicit top-level print'''
      trace('enter implicit_print')
      self.putLine('getstatic java/lang/System/out Ljava/io/PrintStream;', 3)
      self.putLine('swap', 3)
      self.putLine('invokevirtual java/io/PrintStream/println(I)V', 3)
      trace('leave implicit_print')
   def push_terminal(self, token):
      '''Appends Jasmin code to push an integer or constant onto the stack'''
      trace('enter push_terminal')
      self.line = token[2]
      if token[0] == SCAN_TYPES['INT']:
         self.putLine('ldc %d' % token[1], 3)
      else:
         self.putLine('ldc %d      ; %s' % (self.symbol_table[token[1]], \
                                            token[1]), 3)
      trace('leave push_terminal')
   def push_bool(self, value):
      '''Appends Jasmin code to push TRUE (42) or FALSE (0) onto the stack'''
      trace('enter push_bool')
      if value:
         self.putLine('ldc %d      ; TRUE' % self.symbol_table['TRUE'], 3)
      else:
         self.putLine('ldc %d       ; FALSE' % self.symbol_table['FALSE'], 3)
      trace('leave push_bool')
   #
   def unary_plus(self):
      '''Produces code for unary plus'''
      trace('unary plus: no-op')
   def binary_plus(self):
      '''Produces code for binary plus'''
      trace('enter binary_plus')
      self.putLine('iadd', 3)
      trace('leave binary_plus')
   def unary_minus(self):
      '''Produces code for unary minus'''
      trace('enter unary_minus')
      self.putLine('ineg', 3)
      trace('leave unary_minus')
   def binary_minus(self):
      '''Produces code for binary minus'''
      trace('enter binary_minus')
      self.putLine('isub', 3)
      trace('leave binary_minus')
   def binary_mult(self):
      '''Produces code for binary multiply'''
      trace('enter binary_mult')
      self.putLine('imul', 3)
      trace('leave binary_mult')
   def binary_div(self):
      '''Produces code for binary divide'''
      trace('enter binary_div')
      self.putLine('idiv', 3)
      trace('leave binary_div')
   def binary_mod(self):
      '''Produces code for binary mod'''
      trace('enter binary_mod')
      self.putLine('irem', 3)
      trace('leave binary_mod')
   #
   # Relational Operators
   #
   # Note the equivalency of (a), (b), and (c):
   # (a) x < y
   # (b) x - y < y - y
   # (c) x - y < 0
   #
   # Since we are programming a stack machine, the relational operation only
   # comes after each item has been put on the stack. Moreover, Jasmin
   # relational instructions only compare the value on the top of the stack
   # with zero, so all comparisons must be done with respect to zero. We thus
   # use form (c) above for ALL relational operations.
   #
   # The binary_relational method implements a generic template that works
   # with all the Jasmin conditional branch (jump) instructions. This method
   # is simply called with the desired Jasmin jump as its argument.
   #
   def binary_relational(self, jump):
      '''Appends Jasmin code for a conditional jump (branch) instruction'''
      trace('enter binary_relational with jump %s' % jump)
      lbl_true = self.getLabel()
      lbl_end = self.getLabel()
      self.putLine('isub', 3)
      self.putLine('%s %s' % (jump, lbl_true), 3)
      self.push_bool(False)
      self.putLine('goto %s' % lbl_end, 3)
      self.putLine('%s:' % lbl_true, 0)
      self.push_bool(True)
      self.putLine('%s:' % lbl_end, 0)
      trace('leave binary_relational')
   def binary_lt(self):
      '''binary less-than'''
      trace('enter binary_lt')
      self.binary_relational('iflt')
      trace('leave binary_lt')
   def binary_le(self):
      '''binary less-than-or-equal'''
      trace('enter binary_le')
      self.binary_relational('ifle')
      trace('leave binary_le')
   def binary_gt(self):
      '''binary greater-than'''
      trace('enter binary_gt')
      self.binary_relational('ifgt')
      trace('leave binary_gt')
   def binary_ge(self):
      '''binary greater-than-or-equal'''
      trace('enter binary_ge')
      self.binary_relational('ifge')
      trace('leave binary_ge')
   def binary_eq(self):
      '''binary equality'''
      trace('enter binary_eq')
      self.binary_relational('ifeq')
      trace('leave binary_eq')
   def binary_ne(self):
      '''binary inequality'''
      trace('enter binary_ne')
      self.binary_relational('ifne')
      trace('leave binary_ne')
   def unary_not(self):
      '''unary not'''
      trace('enter unary_not')
      # Notice that !x in integer logic is the same expression as (x == 0):
      # !x is true whenever x is false (i.e. x is zero)
      # !x is false whenever x is true (i.e. x is not zero)
      self.output.append('   ldc 0')
      self.binary_eq()
      trace('leave unary_not')
   #
   #
   def trinary_if(self, condition, then_tree, else_tree):
      '''Appends Jasmin code for the trinary if/else expression'''
      trace('enter trinary_if')
      self.putLine('; begin if', 0)
      # Handle the condition first (evaluate the subtree)
      self.handle_subtree(condition)
      # Get labels for else and end if
      lbl_else = self.getLabel()
      lbl_end = self.getLabel()
      # The result of evaluating the condition is now on the top of the stack.
      # Branch to "else" if the tos is zero, otherwise just fall into the
      # "then" branch.
      self.putLine('ifeq %s' % lbl_else, 3)
      self.putLine('; then:', 0)
      # then branch:
      self.handle_subtree(then_tree)
      self.putLine('goto %s' % lbl_end, 3)    # skip else and go to end if
      # else branch:
      self.putLine('%s:' % lbl_else, 0)
      self.putLine('; else:', 0)
      self.handle_subtree(else_tree)
      # end if:
      self.putLine('%s:' % lbl_end, 0)
      self.putLine('; end if', 0)
      #
      trace('leave trinary_if')
   #
   #
   def handle_subtree(self, subtree):
      '''Appends Jasmin code for a subtree or token'''
      trace('enter handle_subtree')
      dbg('subtree: ' + str(subtree))
      if isinstance(subtree, list):
         self.handle_statement(subtree)
      elif isinstance(subtree, tuple):
         self.push_terminal(subtree)
      else:
         trace('leave handle_subtree by exception')
         raise Exception('BUG: handle_subtree got non-list and non-tuple')
      trace('leave handle_subtree')
   def handle_statement(self, statement):
      '''Converts a top-level SLDT statement to Jasmin code'''
      trace('enter handle_statement')
      dbg('statement: ' + str(statement))
      optoken = statement[0]
      args = statement[1:]
      operator = optoken[1]
      self.line = optoken[2]
      argct = len(args)
      trace('operator: %s  argument count: %d' % (operator, argct))
      if operator != 'if':
         # Stack machine is postfix, so need to handle args first
         for arg in args:
            self.handle_subtree(arg)
         dbg('lookup tuple: ' + str((operator, argct)))
         self.oper_map[(operator, argct)]()
      else:
         # "if" is a special case: need to evaluate the first argument
         self.trinary_if(*args)
      trace('leave handle_statement')
   def run(self):
      '''Runs the code generator, either interactively or non-interactively'''
      trace('enter run')
      eof = False
      code = 0
      output = ''
      while not eof:
         try:
            tree, eof = self.type_checker.check()
            if tree != []:
               for statement in tree:
                  self.handle_statement(statement)
                  self.implicit_print()
                  self.output.append('')
               if self.interactive:
                  # Interactive mode: make a method out of each statement
                  print '.method public static main([Ljava/lang/String;)V'
                  stacksize = self.getStackLimit()
                  print '   .limit stack', stacksize
                  print '   .limit locals 1'
                  print ''
                  for line in self.output:
                     print line
                  print '   return'
                  print '.end method'
                  print ''
                  # Now reset the type-checker and clear the output
                  self.type_checker = TypeChecker(self.parser, \
                                                  self.symbol_table)
                  self.output = []
         except CompilerException, e:
            if e.line > 0:
               print >> sys.stderr, self.filename + ':' + str(e.line) + ': ' + \
                                    e.message
            else:
               print >> sys.stderr, self.filename + ': ' + e.message
            code = 4
            if self.interactive:
               # Reset the generator and type-checker if interactive
               print 'Fatal error encountered: resetting compiler'
               print 'Use CTRL+D (CTRL+Z on Windows) to exit'
               print ''
               self.stack = []
               self.type_checker = TypeChecker(self.parser, self.symbol_table)
      #
      if not self.interactive and code == 0:
         # Non-interactive AND successful: print a Jasmin header then
         # encapsulate ALL generated code in the "main" method
         output =  '; Jasmin code generated by SLDT compiler\n'
         output += '; Input file: %s\n\n' % self.filename
         output += '.class public %s\n' % self.classname
         output += '.super java/lang/Object\n\n'
         output += '.method public <init>()V\n'
         output += '   aload_0\n'
         output += '   invokenonvirtual java/lang/Object/<init>()V\n'
         output += '   return\n'
         output += '.end method\n\n'
         output += '.method public static main([Ljava/lang/String;)V\n'
         output += '   .limit stack %d\n' % self.getStackLimit()
         output += '   .limit locals 1\n\n'
         for line in self.output:
            output += line + '\n'
         output += '   return\n'
         output += '.end method'
      trace('leave run')
      return (code, output)
#


if __name__ == '__main__':
   inst = None
   if len(sys.argv) > 1:
      if len(sys.argv) != 3:
         print >> sys.stderr, 'Usage:', sys.argv[0], '<filename>', '<classname>'
         sys.exit(10)
      filename = sys.argv[1]
      classname = sys.argv[2]
      fh = open(filename, 'r')
      inst = CodeGenerator(filename, classname, fh, False)
   else:
      print ('*' * 79)
      print (' ' * 23) + 'Simple LISP Dialect for Teaching'
      print ('*' * 79)
      print 'Generating code in Interactive Mode. Type CTRL+D (CTRL+Z on' + \
            ' Windows) to exit\n'
      inst = CodeGenerator('<stdin>', '', sys.stdin, True)
   code, output = inst.run()
   print output
   sys.exit(code)
#
